//Given a non negative integer number num. For every numbers i in the range 0 ≤ 
//i ≤ num calculate the number of 1's in their binary representation and return th
//em as an array. 
//
// Example 1: 
//
// 
//Input: 2
//Output: [0,1,1] 
//
// Example 2: 
//
// 
//Input: 5
//Output: [0,1,1,2,1,2]
// 
//
// Follow up: 
//
// 
// It is very easy to come up with a solution with run time O(n*sizeof(integer))
//. But can you do it in linear time O(n) /possibly in a single pass? 
// Space complexity should be O(n). 
// Can you do it like a boss? Do it without using any builtin function like __bu
//iltin_popcount in c++ or in any other language. 
// Related Topics 位运算 动态规划 
// 👍 453 👎 0


package editor.cn;

import java.util.Arrays;

//Java：Counting Bits
public class P338CountingBits{
    public static void main(String[] args) {
        Solution solution = new P338CountingBits().new Solution();
        // TO TEST
        int[] ints = solution.countBits(5);
        System.out.println(Arrays.toString(ints));
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] countBits(int num) {
        int[] results = new int[num + 1];
        for (int i = 0; i < num + 1; i++) {
            int temp = i;
            int count = 0;
            while (temp != 0) {
                temp = temp^(temp &((~temp) + 1));
                count++;
            }
            results[i] = count;
        }
        return results;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}